// 快速排序

function quickSort1(arr: number[]): number[] {
    const length = arr.length;
    if (length === 0) return arr;
    const midIndex = Math.floor(length / 2)
    const midValue = arr.splice(midIndex, 1)[0]

    const left: number[] = []
    const right: number[] = []
    for (let i = 0; i < arr.length; i++) {
        const n = arr[i]
        if (n < midValue) {
            left.push(n)
        } else {
            right.push(n)
        }
    }
    return quickSort1(left).concat([midValue], quickSort1(right))
}
function quickSort2(arr: number[]): number[] {
    const length = arr.length;
    if (length === 0) return arr;
    const midIndex = Math.floor(length / 2)
    const midValue = arr.slice(midIndex, midIndex + 1)[0]

    const left: number[] = []
    const right: number[] = []
    for (let i = 0; i < length; i++) {
        if (i !== midIndex) {
            const n = arr[i]
            if (n < midValue) {
                left.push(n)
            } else {
                right.push(n)
            }
        }
    }
    return quickSort2(left).concat([midValue], quickSort2(right))
}

let arr = [1, 4, 5, 6, 9, 7, 10, 8, 0];
console.log(quickSort1(arr));
